#include <vector>
#include <algorithm>
using std::vector;

class Solution {
public:
    int getNum(vector<int>& arr, int target) {
        int sum = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] > target)
                sum += target;
            else
                sum += arr[i];
        }
        return sum;
    }

    int findBestValue(vector<int>& arr, int target) {
        int size = arr.size();
        int sum = 0;
        int max = 1;
        for (int i = 0; i < size; i++) {
            sum += arr[i];
            if (arr[i] > max)
                max = arr[i];
        }
        if (target >= sum)
            return max;

        int left = target / size;
        int right = target - (size - 1) + 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target <= getNum(arr, mid))
                right = mid;
            else
                left = mid + 1;
        }

        if (left == target / size)
            return target / size;
        else
            return abs(target - getNum(arr, left - 1)) > abs(target - getNum(arr, left)) ? left : left - 1;
    }
};